package chain

import "testing"
//leetcode 25题，K个一组翻转链表
type ListNode struct {
	value int
	next  *ListNode
}
//将链表中的k项顺序倒置
//例如： 1->2->3->4->5  k=2: 2->1->4->3->5
func reverseKGroupAnswer(head *ListNode, k int) *ListNode {
	if head == nil || head.next == nil {
		return head
	}

	var (
		dummy = &ListNode{value: 0} //定义一个假的节点。

		//初始化pre和end都指向dummy。
		pre             = dummy //pre指每次要翻转的链表的头结点的上一个节点。
		end             = dummy //end指每次要翻转的链表的尾节点
		start *ListNode = nil   //待翻转片段原始开头
		next  *ListNode = nil   //待翻转片段原始结尾指向的下一个节点（截断的地方）
	)
	//假节点的next指向head。
	// dummy->1->2->3->4->5
	dummy.next = head
	for end.next != nil {
		//循环k次，找到需要翻转的链表的结尾,这里每次循环要判断end是否等于空,因为如果为空，end.next会报空指针异常。
		//dummy->1->2->3->4->5 若k为2，循环2次，end指向2
		for i := 0; i < k && end != nil; i++ {
			end = end.next
		}
		//如果end==null，即需要翻转的链表的节点数小于k，不执行翻转。
		if end == nil {
			break
		}
		//先记录下end.next,方便后面链接链表
		next = end.next
		//然后断开链表
		end.next = nil
		//记录下要翻转链表的头节点
		start = pre.next
		//翻转链表,pre.next指向翻转后的链表。1->2 变成2->1。 dummy->2->1
		pre.next = reverse(start)
		//翻转后头节点变到最后。通过.next把断开的链表重新链接。
		start.next = next
		//将pre换成下次要翻转的链表的头结点的上一个节点。即start
		pre = start
		//翻转结束，将end置为下次要翻转的链表的头结点的上一个节点。即start
		end = start
	}
	return dummy.next
}

//链表翻转
// 例子：   head： 1->2->3->4
func reverse(head *ListNode) *ListNode {
	//单链表为空或只有一个节点，直接返回原单链表
	if head == nil || head.next == nil {
		return head
	}
	var (
		preNode  *ListNode = nil  //前一个节点指针
		curNode            = head //当前节点指针
		nextNode *ListNode = nil  //下一个节点指针
	)
	for curNode != nil {
		nextNode = curNode.next //nextNode 指向下一个节点,保存当前节点后面的链表。
		curNode.next = preNode  //将当前节点next域指向前一个节点   null<-1<-2<-3<-4
		preNode = curNode       //preNode 指针向后移动。preNode指向当前节点。
		curNode = nextNode      //curNode指针向后移动。下一个节点变成当前节点
	}
	return preNode
}

func TestReverse(t *testing.T){
	var (
		t5=&ListNode{value: 5,next:nil}
		t4=&ListNode{value: 4,next:t5}
		t3=&ListNode{value: 3,next:t4}
		t2=&ListNode{value: 2,next:t3}
		t1=&ListNode{value: 1,next:t2}
	)
	LogChain(t1)
}